﻿/*
参考文档：
[1] 全排列研究文档 https://ai-cyber-security.feishu.cn/docx/U4sbdJKS8obV16xEqQ5cGci6n3f


*/
namespace ConsoleAlgorithms.Utils
{

    public class BackTrackPermutation : ITestable
    {
        public void Test()
        {
            var root = new TreeNode(0);
            List<int> data = new List<int>();
            data.Add(1);
            data.Add(2);
            data.Add(3);
            data.Add(4);
            TreeNode.traverse(root, data);
            TreeNode.print(root, 0);

            List<int> vs = new List<int>();
            TreeNode.traverseNodes(root, vs);

            TreeNode.printTree(root);
        }
    }

    public class TreeNode
    {
        public TreeNode parent;
        public List<TreeNode> nodes = new List<TreeNode>();
        public List<int> data = new List<int>();
        public int v;

        public TreeNode() { }
        public TreeNode(int v) { this.v = v; }


        public void add(int value)
        {
            TreeNode tn = new TreeNode(value);
            this.nodes.Add(tn);
            tn.parent = this;
        }

        public static void traverse(TreeNode tn, List<int> values)
        {
            for (int i = 0; i < values.Count; i++)
            {
                var vs = Clone(values);
                var node = new TreeNode(vs[i]);
                vs.RemoveAt(i);
                tn.nodes.Add(node);
                node.parent = tn;
                traverse(node, vs);
            }
        }

        public static void print(TreeNode tn, int level)
        {
            for (int i = 0; i < level; i++)
                Console.Write(" ");
            Console.WriteLine(tn.v);

            for (int i = 0; i < tn.nodes.Count; i++)
            {
                print(tn.nodes[i], level + 1);
            }
        }


        public static void traverseNodes(TreeNode tn, List<int> values)
        {
            if (tn.nodes.Count == 0)
                Console.WriteLine(ToStrings(values));

            for (int i = 0; i < tn.nodes.Count; i++)
            {
                values.Add(tn.nodes[i].v);
                traverseNodes(tn.nodes[i], values);
                values.RemoveAt(values.Count - 1);
            }
        }

        public static List<int> Clone(List<int> vs)
        {
            List<int> results = new List<int>();
            for (int i = 0; i < vs.Count; i++)
                results.Add(vs[i]);
            return results;
        }

        public static String ToStrings(List<int> vs)
        {
            String[] values = new String[vs.Count];
            for (int i = 0; i < vs.Count; i++)
                values[i] = vs[i] + "";
            return "[" + string.Join(", ", values) + "]";
        }

        static string s1 = "├─";
        static string s2 = "└─";

        // ref: https://ai-cyber-security.feishu.cn/docx/U4sbdJKS8obV16xEqQ5cGci6n3f
        public static void printTree(TreeNode tn)
        {
            Console.WriteLine(tn.v);
            List<string> ancestors = new List<string>();
            foreach (var node in tn.nodes)
                print(node, ancestors);
        }

            // │ ├ ─ └ 
        public static void print(TreeNode tn, List<string> ancestors)
        {
            string head = s1; 
               if (tn == tn.parent.nodes[tn.parent.nodes.Count - 1])
                head = s2;
            Console.WriteLine(string.Join("", ancestors) + head + tn.v);

            foreach (var node in tn.nodes)
            {
                ancestors.Add(head == s1 ? "│  " : "   ");
                print(node, ancestors);
                ancestors.RemoveAt(ancestors.Count - 1);
            }
        }
    }

}
